package p100;

public class Leetcode_124 {

    /**
     * Definition for a binary tree node.
     */
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    private int max = Integer.MIN_VALUE;

    private int maxPathSum(TreeNode root) {
        getMax(root);
        return max;
    }

    private int getMax(TreeNode r) {
        if (r == null) return 0;
        int left = getMax(r.left);
        int right = getMax(r.right);
        max = Math.max(max, r.val + left + right);
        int res = r.val + Math.max(left, right);
        return res > 0 ? res : 0;
    }

    public static void main(String[] args) {

    }
}
